package interview.hw_od;

import java.util.*;

/**
 * 阿里巴巴找黄金宝箱(Ⅱ) https://zhuanlan.zhihu.com/p/642686464
 * https://codefun2000.com/p/P1328
 * 题目简述：一贫如洗的樵夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从0-N的箱子，
 * 每个箱子上面贴有箱子中藏有金币Q的数量。 从金币数量中选出一个数字集合，并销毁贴有这些数字的每个箱子，
 * 如果能销毁一半及以上的箱子，则返回这个数字集合的最小大小
 */
public class AlibabaGoldBox2 {

    /**
     * 思路：即从数组中选出占比最大的几个数字，使它们总占比等于或超过一半
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split(",");
        int[] nums = new int[s.length];
        for (int i = 0;i < s.length;i++) {
            nums[i] = Integer.parseInt(s[i]);
        }
        //统计每种数字的数量
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        //按每种数字的数量降序排序
        list.sort((o1, o2) ->  o2.getValue() - o1.getValue());
        int n = (s.length+1)/2;//需销毁的箱子数
        for (int i = 0;i < list.size();i++) {
            n -= list.get(i).getValue();
            if (n <= 0) {
                //当n<=0输出i+1并终止循环
                System.out.println(i+1);
                break;
            }
        }
    }
}
